
// 结构体存储：空闲时间、是否已经安排了挑水时间

#include<stdio.h>

int water[7] = { 0 };

typedef struct monk
{
	int sparetime[8];
	int flag;//用于判断是否已经安排挑水，回溯的时候使用。
}MK;

void init(MK* m)
{
	m->flag = 0;//没挑过水
	int i;
	for (i = 1; i < 8; i++)
	{
		m->sparetime[i] = 0;//0有空，1没空 
	}
}

int check(int day)
{
	int k;
	for (k = 0; k < 7; k++)
	{
		if (water[k] == day)
		{
			//有人安排了这天，继续看这个和尚有没有别的空闲时间
			break;
		}
	}
	return k;
}

int main()
{
	MK m[7];
	int i;
	//初始化 
	for (i = 0; i < 7; i++)
	{
		init(&m[i]);
	}
	//时间输入 
	m[0].sparetime[2] = 1;//一号和尚 ，星期二有空 
	m[0].sparetime[4] = 1;

	m[1].sparetime[1] = 1;//二号和尚
	m[1].sparetime[6] = 1;

	m[2].sparetime[3] = 1;
	m[2].sparetime[7] = 1;

	m[3].sparetime[5] = 1;

	m[4].sparetime[1] = 1;
	m[4].sparetime[4] = 1;
	m[4].sparetime[6] = 1;

	m[5].sparetime[2] = 1;
	m[5].sparetime[5] = 1;


	m[6].sparetime[3] = 1;
	m[6].sparetime[6] = 1;
	m[6].sparetime[7] = 1;


	//直接从第一个和尚的空闲时间开始寻找，找到后就进行下一个和尚时间的安排
	//安排的时候，先遍历water数组，看是否有别的和尚已经安排了这天，若有，则继续检测和尚的空闲时间
	//若没有其余空闲时间（循环后flag==1），就需要回溯到上一个和尚（i--），寻找另外的空闲时间，直至全部和尚都有安排
	int j, k;
	for (i = 0; i < 7; i++)
	{
		for (j = 1; j < 8; j++)
		{
			m[i].flag = 0;
			if (water[i] != 0)
			{
				j = water[i] + 1;
				water[i] = 0;
			}
			if (m[i].sparetime[j] == 1)//找到第i+1的和尚的星期j为空闲时间 
			{

				int ret = check(j);//返回冲突的和尚
				if (ret == 7)//没有和尚重复-不再寻找别的时间
				{
					//确定挑水时间
					m[i].flag = 1;
					water[i] = j;//第i+1个和尚星期j挑水
					break;
				}
				else
				{
					continue;
				}
			}
		}
		if (m[i].flag == 0)//没有其余空闲时间，需要回溯安排上一个和尚的另外的空闲时间，通过water[i]找到之前安排的日期
		{
			i -= 2;
		}
	}

	for (k = 0; k < 7; k++)
	{
		printf("%d号和尚在星期%d打水\n", k + 1, water[k]);
	}
	return 0;
}










